1556E - Equilibrium - CodeForces Solution

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int mx = 1e5+5;
int a[mx], b[mx];
ll n, q, mmin[20][mx], c[mx], mmax[20][mx];

long long getmin(int l, int r) {
    int lv=31^__builtin_clz(r-l+1);
    return min(mmin[lv][l+(1<<lv)-1], mmin[lv][r]);
}
long long getmax(int l, int r) {
    int lv=31^__builtin_clz(r-l+1);
    return max(mmax[lv][l+(1<<lv)-1], mmax[lv][r]);
}

int main() {
    cin >> n >> q;
    for (int i=0; i<n; i++) cin >> a[i];
    for (int i=0; i<n; i++) cin >> b[i];
    for (int i=0; i<n; i++) c[i+1] = c[i] - a[i] + b[i];
    for (int i=1; i<=n; i++) mmin[0][i] = mmax[0][i] = c[i];
    for (int i=0; 2<<i<=n; i++) {
        for (int j=2<<i; j<=n; j++) {
            mmin[i+1][j] = min(mmin[i][j], mmin[i][j-(1<<i)]);
            mmax[i+1][j] = max(mmax[i][j], mmax[i][j-(1<<i)]);
        }
    }
    while (q--) {
        int l, r; cin >> l >> r;
        if (c[r] != c[l-1] || getmin(l, r) < c[l-1]) cout << "-1\n";
        else cout << getmax(l, r) - c[l-1] << "\n";
    }
}